/**
 * 
 */
package solution.dp;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

import junit.framework.Assert;

import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 */
public class SplitStringToWords {

	class Dictionary {
		int maxLen = 0;

		Set<String> wordSet = new HashSet<String>();

		public Dictionary(String[] dict) {
			maxLen = 0;
			for (String s : dict) {
				wordSet.add(s);
				if (s.length() > maxLen) {
					maxLen = s.length();
				}
			}
		}

		/**
		 * @return the maxLen
		 */
		public int getMaxLen() {
			return maxLen;
		}

		public boolean hasWord(String wd) {
			return wordSet.contains(wd);
		}
	}

	int cache[];

	Dictionary dict;

	Stack<String> stk;

	char[] wdArr;

	public SplitStringToWords() {
	}

	/**
	 * @param dict
	 *            the dict to set
	 */
	public void setDict(String[] dict) {
		this.dict = new Dictionary(dict);
	}

	public int splitWords(String longString) {
		wdArr = longString.toCharArray();

		// cache the result. the top-down DP comes into play
		cache = new int[wdArr.length];
		Arrays.fill(cache, -1); // initialize the cache.

		// for words being split out
		stk = new Stack<String>();
		return splitWords_rec(0);
	}

	/**
	 * split string into words staring from 'pos'
	 * 
	 * @param pos
	 * @return
	 */
	int splitWords_rec(int pos) {
		if (pos >= wdArr.length)
			return 0;

		// if it is already cached, don't bother calculate it again.
		if (cache[pos] >= 0)
			return cache[pos];

		int splits = 0;

		for (int len = 1; len <= dict.getMaxLen() && len + pos <= wdArr.length; len++) {
			// check if current string starts with a word in the dictionary
			String wd = String.valueOf(wdArr, pos, len);
			if (!dict.hasWord(wd)) {
				continue;
			}

			// if this word ends the whole string, we have found one split
			if (pos + len == wdArr.length) {
				stk.push(wd);
				// System.out.println(StringUtils.join(q, ","));
				stk.pop();
				splits++;
				continue;
			}

			// go ahead and split the string to the end.
			stk.add(wd);
			splits += splitWords_rec(pos + len);
			stk.remove(stk.size() - 1);
		}
		cache[pos] = splits;
		return splits;
	}

	@Test
	public void test() {
		SplitStringToWords splitStringToWords = new SplitStringToWords();
		splitStringToWords.setDict(new String[] //
				{ "aaa", "bb", "cc", "aaabb", "bbcc" });
		Assert.assertEquals(3, splitStringToWords.splitWords("aaabbcc"));

		splitStringToWords.setDict(new String[] //
				{ "a", "aa", "aaa", "aaaa", "aaaaa" });
		Assert.assertEquals(1, splitStringToWords.splitWords("a"));
		Assert.assertEquals(2, splitStringToWords.splitWords("aa"));
		Assert.assertEquals(4, splitStringToWords.splitWords("aaa"));
		Assert.assertEquals(8, splitStringToWords.splitWords("aaaa"));
		Assert.assertEquals(16, splitStringToWords.splitWords("aaaaa"));
	}
}
